package com.zhuiyi.yiqingbackend.leetcod;

public class Solution {
    public String greatestLetter(String s) {
        int n = s.length();
        int[] count = new int[52];
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            if (c >= 'a' && c <= 'z') {
                count[c - 'a']++;
            } else if (c >= 'A' && c <= 'Z') {
                count[c - 'A' + 26]++;
            }
        }
        String res = "";
        for (int i = 51; i >=26; i--) {
            if (count[i] > 0 && count[i - 26] >0) {
                return (char) (i + 'A' - 26)+"";
            }
        }

        return res;
    }
    /**
     * 个位数字为 K 的整数之和 显示英文描述
     * 通过的用户数2443
     * 尝试过的用户数3367
     * 用户总通过次数2474
     * 用户总提交次数11924
     * 题目难度Medium
     * 给你两个整数 num 和 k ，考虑具有以下属性的正整数多重集：
     *
     * 每个整数个位数字都是 k 。
     * 所有整数之和是 num 。
     * 返回该多重集的最小大小，如果不存在这样的多重集，返回 -1 。
     *
     * 注意：
     *
     * 多重集与集合类似，但多重集可以包含多个同一整数，空多重集的和为 0 。
     * 个位数字 是数字最右边的数位。
     */
    public int sumOfDigits(int num, int k) {
        int []recoder = new int[3001];
        for (int i=1;i<3001;i++){
            if(i%10==k){
                recoder[i]=i;
            }
        }
        int res = 0;

        return num==0?res:-1;
    }

    /**
     *  Longest Binary Subsequence Less Than or Equal to K 显示英文描述
     * 通过的用户数1000
     * 尝试过的用户数1643
     * 用户总通过次数1023
     * 用户总提交次数3501
     * 题目难度Medium
     * You are given a binary string s and a positive integer k.
     *
     * Return the length of the longest subsequence of s that makes up a binary number less than or equal to k.
     *
     * Note:
     *
     * The subsequence can contain leading zeroes.
     * The empty string is considered to be equal to 0.
     * A subsequence is a string that can be derived from another string by deleting some or no characters without changing the order of the remaining characters.
     *
     */

    public int longestSubsequence(String s, int k) {
        int n = s.length();
        int[] dp = new int[n];
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
            for (int j = i - 1; j >= 0; j--) {
                if (s.charAt(i) == s.charAt(j) && dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j] + 1;
                }
            }
        }
        int res = 0;
        for (int i = 0; i < n; i++) {
            if (dp[i] <= k) {
                res = Math.max(res, dp[i]);
            }
        }
        return res;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
//        System.out.println(solution.longestSubsequence("00101001", 1));
        System.out.println(solution.sumOfDigits(58, 9));
    }
}
